package com.outsider.tool.rsa;
/**
 * 扩展欧几里得工具类
 * 求解ax+by= gcd(a, b)
 * O(常数？)
 * @author outsider
 *
 */
public class Exgcd {
	private int a,b,x,y;
	public Exgcd(int a,int b){
		this.a=a; this.b=b; x=0; y=0;
		calculate(a,b);
		
	}
	public int calculate(int a,int b){
		   if (b==0){
			   x=1;
			   y=0;
			   return a;
		   }
		   int ans=calculate(b,a%b);
		   int temp=x;
		   x=y;
		   y=temp-a/b*y;
		   return ans;
	   }
	public int getX() {
		return x;
	}
	public int getY() {
		return y;
	}
}
